МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
Національний університет “Львівська політехніка”
Особливості розв’язку транспортної задачі
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи № 3
з курсу “Методи синтезу та оптимізації”
для студентів базового напряму 6.08.04 “Компютерні науки”
ЗАТВЕРДЖЕНО
На засіданні кафедри САП
Протокол № 1 від 28.08.2008 р.
ЛЬВІВ 2008
Особливості розв’язку транспортної задачі. Методичні вказівки до лабораторної роботи № 3 з курсу “Методи синтезу та оптимізації” для студентів базового напряму 6.08.04 “Компютерні науки” /Укл. Теслюк В. М., Андрійчук М. І. – Львів: НУ “ЛП”, 2008 р.
Укладачі: Теслюк Василь Миколайович, к. т. н., доцент;
Андрійчук Михайло Іванович, к. ф.-м., доцент.
Відповідальний за випуск: Ткаченко С. П., к. т. н., доцент.
Рецензенти: Каркульовський В. І., к.т. н., доцент,
Стех Ю. В., к.т. н., доцент.
1. МЕТА РОБОТИ
Ознайомитися з особливостями розв’язування транспортної задачі.
2. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ
Транспортна задача (модель) відноситься до задач лінійного програмування. Під транспортною моделлю розуміють задачу, яка використовується для вирішення задачі побудови найбільш економічного плану перевозок одного виду продукції з декількох пунктів (для прикладу склади, заводи тощо) в пункти призначення (торгові організації, ті ж склади та ін). Разом з тим, дану модель з успіхом використовують при вирішенні ряду інших задач зокрема: керування запасами, побудови сіткових графіків, призначенням службовців на посади, регулюванні витрат води та ін.
Оскільки транспортна задача відноситься до задач ЛП, то для її розв’язку можна використати симплекс-метод, який розглянуто вище. Однак специфічна структура цієї задачі дозволяє розробити більш простіші та ефективні методи для її вирішення. Хоча, при розв’язку транспортної задачі використовується такий же алгоритм як і при використанні симплекс-методу.
2.1 Постановка транспортної задачі
Отже, як було зазначено вище, при постановці транспортної задачі необхідно побудувати найбільш економічний план перевозок одного виду продукції з декількох пунктів (кількість яких позначимо через I, а кількість продукції, яка виробляється в кожному пункті - ) в пункти призначення (кількість яких позначимо через J, а кількість продукції, яку необхідно обов’язково підвести до кожного пункта - ), вартість перевезення однієї одиниці продукції з пункта i в пункт j позначимо через , а через - позначимо кількість продукції, яку необхідно перевести з пункта i в пункт призначення j. Тепер усі вхідні дані є і сформулюємо транспортну задачу в загальному випадку:
, (2.1)
при виконанні наступних обмежень:
, , (2.2)
, ,
, для всіх i та j.
В даній постановці перша група обмежень вказує на те, що сумарна кількість продукції вивезеної з певного пункта-джерела не може перевищувати кількість продукції, яка в ньому вироблена, а друга – вимагає щоб сумарні перевезення в деякий пункт повністю задовільнями попит цього пункта.
2.2 Поняття збалансованою та незбалансованої транспортної задачі
З наведеної постановки транспортної задачі (2.1, 2.2) слідує, що сумарний об’єм виготовлення продукції в пунктах не має бути меншим сумарного попиту в пунктах призначення . У випадку, коли , то така транспортна задача називається збалансованою, а транспортна задача в якої називається незбалансованою. Вона відрізняється від вищенаведеної тим, що всі обмеження перетворюються в рівності, а саме:
, , (2.3)
, .
Збалансованість реальної транспортної задачі є дуже важливою ознакою, яка значно спрощує розв’язок задачі. Тому, на практиці, завжди стараються збалансувати транспортну задачу. Наведемо приклад транспортної задачі.
Нехай автомобілі певної марки виготовляють на заводах З1, З2 і З3. Об’єми виробництва складають відповідно 300, 400, 700 автомобілів кожного місяця. Параметри щомісячного попиту на автомобілі даної марки в магазинах М1 і М2 складають 1000 і 400 шт. відповідно. Вартість перевезення одного автомобіля на оди...
